package leetcode_100;

/**
 *@author 周杨
 *LongestPalindromicSubstring_5 在一个串中找最长的回文串  
 *describe:可以用动态规划 最佳方法是马拉车 时间可以控制在O(n)里解决
 *2018年9月9日 下午4:17:30
 */
public class LongestPalindromicSubstring_5 {
	
	public static void main(String[] args) {
		LongestPalindromicSubstring_5 test=new LongestPalindromicSubstring_5();
		System.out.println(test.longestPalindrome("abbbbbaccc"));
		System.out.println(test.longestPalindrome(""));
		System.out.println(test.longestPalindrome("a"));
		System.out.println(test.longestPalindrome("abbaccccccca"));
	}
	
	/**
	 * describe:动态规划解 一个串是否是回文串的递归问题是 左右两边相等 中间是回文串 AC 50%
	 * 2018年9月9日 下午4:03:58
	 */
	public String longestPalindrome(String s) {
		if(s.length()==0)
			return "";
		char [] chars=s.toCharArray();
		int left=0,right=0,len=0;
		boolean dp[][]=new boolean[s.length()][s.length()];
		for(int i=0;i<s.length();++i) {
			dp[i][i]=true;
			for(int j=0;j<i;++j) {
				if(chars[i]==chars[j]&&(i-j==1||dp[j+1][i-1]))
					dp[j][i]=true;
				if(dp[j][i]&&i-j>len) {
					left=j;
					right=i;
					len=right-left;
				}
			}
		}
		return s.substring(left, right+1);
	}
	
	
	 /**
	 * describe:AC 百分之11 暴力解
	 * 2018年9月9日 下午2:18:14
	 */
	public String longestPalindrome1(String s) {
	     int resultLength=0;
	        String result="";
	        int len=s.length();
	        for(int i=0;i<s.length();++i){
	            if(resultLength==len-i+1)
	                return result;//如果接下来不可能有比当前字符串长 立即结束
	            for(int j=len-i;j>resultLength;--j){//判断是否是回字符
	            		if(judge(s,i,j)){
	            			result=s.substring(i, i+j);
	            			resultLength=j;
	            		}
	            }
	        }
	        return result;
	    }
	    public  boolean judge(String s,int i,int j){
			int be=i,af=i+j-1;
			while(be<af){
				if(s.charAt(be)!=s.charAt(af))
					return false;
				++be;
				--af;
			}
			return true;
		}
}
